package leetcode_acm.string;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月22日 10:12
 */
public class ReverseWords {
    public String reverseWords(String s) {
        //1. 先对整个字符串进行反转
        char[] str = s.toCharArray();
        reverse(str,0,str.length);
        //2. 然后开始搜索边界
        int begin = 0,end = str.length-1;
        while(str[begin] == ' '){
            begin++;
        }
        while (str[end] == ' '){
            end--;
        }
        //3.开始依次反转字符串,使用的核心算法是双指针算法
        int slow = begin -1 ,fast = begin;
        int lastIndex = begin;
        while(fast <= end){
            while(str[fast] == ' ' && str[fast+1] == ' '){
                fast++;
            }
            if(str[fast] == ' ' && str[fast+1] != ' '){
                reverse(str,lastIndex,slow+1);
                lastIndex = slow +2;
            }
            str[++slow] = str[fast++];
        }
        reverse(str,lastIndex,slow+1);
        return new String(str,begin,(slow-begin)+1);
    }
    private void reverse(char[] str,int l,int r){
        for(int i = l,j = r-1;i < j;i++,j--){
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }
}
